/*
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

/*
 *
 *
 *
 *
 *
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

package java.util.concurrent.locks;

import java.util.concurrent.TimeUnit;
import java.util.Collection;


/**
 * 读写锁(共享模式锁)

 *  A、读写分离
 *  B、读读不互斥
 *  C、读写互斥
 *  D、写写互斥
 *  E、既可以是公平锁，也可以是非公平锁
 
 * 1、可重入的
 * 2、支持公平和非公平的获取锁的方式
 * 3、支持超时或者响应中断的，读取锁和写入锁都支持锁获取期间的中断
 * 4、Condition支持，仅写入锁提供了Condition实现，读取锁不支持Condition，readLock().newCondition()会抛出异常。
 * 5、ReentrantReadWriteLock是依赖AQS来实现的
 * 6、与ReentrantLock最大的不同点是，ReentrantLock是独占锁，而ReentrantReadWriteLock不是。
 * 7、有读锁与写锁这两把锁。而ReentrantLock只是一把锁。
 */
public class ReentrantReadWriteLock implements ReadWriteLock, java.io.Serializable {

    private static final long serialVersionUID = -6992448646407690164L;

    /**
     * 读锁
     */
    private final ReentrantReadWriteLock.ReadLock readerLock;

    /**
     * 写锁
     */
    private final ReentrantReadWriteLock.WriteLock writerLock;

    /**
     * 执行的同步机制
     */
    final Sync sync;


    // 空参构造,默认非公平锁
    public ReentrantReadWriteLock() {
        this(false);
    }

    // 有参构造, true:公平锁 false:非公平锁
    public ReentrantReadWriteLock(boolean fair) {
        sync = fair ? new FairSync() : new NonfairSync();
        readerLock = new ReadLock(this);
        writerLock = new WriteLock(this);
    }

    // get方法
    public ReentrantReadWriteLock.WriteLock writeLock() {
        return writerLock;
    }

    public ReentrantReadWriteLock.ReadLock readLock() {
        return readerLock;
    }


    /**
     * ReentrantReadWriteLock 的同步实现。 分为公平和非公平版本。
     */
    abstract static class Sync extends AbstractQueuedSynchronizer {
        private static final long serialVersionUID = 6317671515068378041L;

        static final int SHARED_SHIFT = 16;
        static final int MAX_COUNT = (1 << SHARED_SHIFT) - 1;       // 65535

        // 写锁,独占模式
        static final int SHARED_UNIT = (1 << SHARED_SHIFT);         // 65536
        // 读锁,共享模式
        static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;  // 65535

        /**
         * 返回以计数表示的共享持有数
         *  对于 x = 0，x >>> 16 的结果是 0
         *  对于 x = 1，x >>> 16 的结果是 0
         *  对于 x = 65536，x >>> 16 的结果是 1
         *  对于 x = -1，x >>> 16 的结果是 65535
         */
        static int sharedCount(int c) {
            return c >>> SHARED_SHIFT;
        }

        /**
         * 返回以计数表示的独占保留数
         *  获取写状态值
         *  当 c = 0       时, w = c & 65535 = 0,  说明没有写锁,同时也没有读锁
         *  当 c >  65535  时, w = c & 65535 = 0,  说明没有写锁,但是存在读锁,读锁下也可进入独占模式
         *  当 c <= 65535  时, w = c & 65535 = c,  说明存在写锁,进行重入
         */
        static int exclusiveCount(int c) {
            return c & EXCLUSIVE_MASK;
        }

        /**
         * 每个线程读取保持计数的计数器。作为受威胁的本地维护；缓存在cachedHoldCounter中
         */
        static final class HoldCounter {
            int count = 0;
            // 使用id，而不是引用，以避免垃圾保留
            final long tid = getThreadId(Thread.currentThread());
        }

        /**
         * ThreadLocal subclass. Easiest to explicitly define for sake
         * of deserialization mechanics.
         */
        static final class ThreadLocalHoldCounter
                extends ThreadLocal<HoldCounter> {
            public HoldCounter initialValue() {
                return new HoldCounter();
            }
        }

        /**
         * The number of reentrant read locks held by current thread.
         * Initialized only in constructor and readObject.
         * Removed whenever a thread's read hold count drops to 0.
         */
        private transient ThreadLocalHoldCounter readHolds;

        /**
         * The hold count of the last thread to successfully acquire
         * readLock. This saves ThreadLocal lookup in the common case
         * where the next thread to release is the last one to
         * acquire. This is non-volatile since it is just used
         * as a heuristic, and would be great for threads to cache.
         *
         * Can outlive the Thread for which it is caching the read
         * hold count, but avoids garbage retention by not retaining a
         * reference to the Thread.
         *
         * Accessed via a benign data race; relies on the memory
         * model's final field and out-of-thin-air guarantees.
         */
        private transient HoldCounter cachedHoldCounter;

        /**
         * firstReader：获取读锁的第一个线程
         */
        private transient Thread firstReader = null;
        /**
         * firstReaderHoldCount：第一个读线程持有读锁的重入次数
         */
        private transient int firstReaderHoldCount;

        Sync() {
            readHolds = new ThreadLocalHoldCounter();
            setState(getState()); // ensures visibility of readHolds
        }

        /*
         * Acquires and releases use the same code for fair and
         * nonfair locks, but differ in whether/how they allow barging
         * when queues are non-empty.
         */

        /**
         * 如果当前线程在尝试获取读锁时,并且有资格获取读锁
         *  由于超越其他等待线程的策略而应该阻塞,则返回true
         */
        abstract boolean readerShouldBlock();

        /**
         * Returns true if the current thread, when trying to acquire
         * the write lock, and otherwise eligible to do so, should block
         * because of policy for overtaking other waiting threads.
         */
        abstract boolean writerShouldBlock();

        /*
         * Note that tryRelease and tryAcquire can be called by
         * Conditions. So it is possible that their arguments contain
         * both read and write holds that are all released during a
         * condition wait and re-established in tryAcquire.
         */

        protected final boolean tryRelease(int releases) {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            int nextc = getState() - releases;
            boolean free = exclusiveCount(nextc) == 0;
            if (free)
                setExclusiveOwnerThread(null);
            setState(nextc);
            return free;
        }


        /**
         * 加锁
         */
        protected final boolean tryAcquire(int acquires) {
            // 获取当前线程
            Thread current = Thread.currentThread();
            // 获取同步状态
            int c = getState();
            // 获取写状态值
            // 当 c = 0       时, w = c & 65535 = 0,  说明没有写锁,同时也没有读锁
            // 当 c >  65535  时, w = c & 65535 = 0,  说明没有写锁,但是存在读锁,读锁下也可进入独占模式
            // 当 c <= 65535  时, w = c & 65535 = c,  说明存在写锁,进行重入
            int w = exclusiveCount(c);


            // 若 c != 0, 说明线程持有同步状态,即线程获取了读锁或者写锁
            if (c != 0) {
                // (Note: if c != 0 and w == 0 then shared count != 0)
                // 这个判断说明,读锁已经持有,或者当前线程不是持有锁的线程,则返回获取锁失败
                if (w == 0 || current != getExclusiveOwnerThread())
                    return false;
                // 代码走到这里可能有以下情况
                // if (w != 0 && current =  getExclusiveOwnerThread())
                // 当前线程持有写锁,并重入逻辑

                // 当w != 0 或者 当前线程是持有锁的线程，进行下面操作
                // 如果重入读锁的次数超过限制，抛出异常
                if (w + exclusiveCount(acquires) > MAX_COUNT)
                    throw new Error("Maximum lock count exceeded");
                // 设置同步状态为写锁获重入次数
                setState(c + acquires);
                return true;
            }

            // 走到这步, 同步状态为0,表示读锁或者写锁都未持有
            if (
                // 写线程应该被阻止
                    writerShouldBlock() ||
                            // CAS设置同步状态失败,则返回false
                            !compareAndSetState(c, c + acquires)) {
                return false;
            }

            // 获取写锁成功,设置当前线程未独占线程
            setExclusiveOwnerThread(current);
            return true;
        }

        protected final boolean tryReleaseShared(int unused) {
            Thread current = Thread.currentThread();
            if (firstReader == current) {
                // assert firstReaderHoldCount > 0;
                if (firstReaderHoldCount == 1)
                    firstReader = null;
                else
                    firstReaderHoldCount--;
            } else {
                HoldCounter rh = cachedHoldCounter;
                if (rh == null || rh.tid != getThreadId(current))
                    rh = readHolds.get();
                int count = rh.count;
                if (count <= 1) {
                    readHolds.remove();
                    if (count <= 0)
                        throw unmatchedUnlockException();
                }
                --rh.count;
            }
            for (; ; ) {
                int c = getState();
                int nextc = c - SHARED_UNIT;
                if (compareAndSetState(c, nextc))
                    // Releasing the read lock has no effect on readers,
                    // but it may allow waiting writers to proceed if
                    // both read and write locks are now free.
                    return nextc == 0;
            }
        }

        private IllegalMonitorStateException unmatchedUnlockException() {
            return new IllegalMonitorStateException(
                    "attempt to unlock read lock, not locked by current thread");
        }


        /**
         * 共享模式下加锁
         *  1、如果写锁被另一个线程持有,则失败
         *  2、否则,该线程有资格获得lock wrt状态，因此询问它是否应该因为队列策略而阻塞
         *  3、如果步骤 2 由于线程明显不合格或 CAS 失败或计数饱和而失败，则链接到具有完整重试循环的版本
         */
        protected final int tryAcquireShared(int unused) {

            // 获取当前线程
            Thread current = Thread.currentThread();
            // 获取同步状态
            int c = getState();
            // 写状态不能为(有写锁),并且当前线程并没有持有锁,则设置读锁失败
            if (exclusiveCount(c) != 0 && getExclusiveOwnerThread() != current)
                return -1;


            /*
             * 走到这里,会有几种情况
             *   1、当前线程持有锁重入     c != 0 && c < 65535
             *   2、任何线程都没有持有锁   c == 0
             *
             * 返回以计数表示的共享持有数
             *  对于 x = 0，x >>> 16 的结果是 0
             *  对于 x = 1，x >>> 16 的结果是 0
             *  对于 x = 65536，x >>> 16 的结果是 1
             *  对于 x = -1，x >>> 16 的结果是 65535
             */
            int r = sharedCount(c);


            // 1、判断读线程是否应该被堵塞
            // 2、判断读状态释放超过最大值
            // 3、CAS设置同步状态释放成功
            if (!readerShouldBlock() &&
                    r < MAX_COUNT &&
                    compareAndSetState(c, c + SHARED_UNIT)) {

                // 上面已经判断过写状态为0，此时如果读状态为0，表示可以直接获取读锁
                if (r == 0) {
                    // firstReader：获取读锁的第一个线程
                    firstReader = current;
                    // firstReaderHoldCount：第一个读线程持有读锁的重入次数
                    firstReaderHoldCount = 1;
                } else if (firstReader == current) {
                    firstReaderHoldCount++;
                }
                //下面一段代码的作用是 记录每一个读线程获取读锁的重入次数
                else {
                    HoldCounter rh = cachedHoldCounter;
                    if (rh == null || rh.tid != getThreadId(current))
                        cachedHoldCounter = rh = readHolds.get();
                    else if (rh.count == 0)
                        readHolds.set(rh);
                    rh.count++;
                }
                return 1;
            }

            // 完全尝试获取共享
            return fullTryAcquireShared(current);
        }

        /**
         * Full version of acquire for reads, that handles CAS misses
         * and reentrant reads not dealt with in tryAcquireShared.
         */
        final int fullTryAcquireShared(Thread current) {
            /*
             * This code is in part redundant with that in
             * tryAcquireShared but is simpler overall by not
             * complicating tryAcquireShared with interactions between
             * retries and lazily reading hold counts.
             */
            HoldCounter rh = null;
            for (; ; ) {
                int c = getState();
                if (exclusiveCount(c) != 0) {
                    if (getExclusiveOwnerThread() != current)
                        return -1;
                    // else we hold the exclusive lock; blocking here
                    // would cause deadlock.
                } else if (readerShouldBlock()) {
                    // Make sure we're not acquiring read lock reentrantly
                    if (firstReader == current) {
                        // assert firstReaderHoldCount > 0;
                    } else {
                        if (rh == null) {
                            rh = cachedHoldCounter;
                            if (rh == null || rh.tid != getThreadId(current)) {
                                rh = readHolds.get();
                                if (rh.count == 0)
                                    readHolds.remove();
                            }
                        }
                        if (rh.count == 0)
                            return -1;
                    }
                }
                if (sharedCount(c) == MAX_COUNT)
                    throw new Error("Maximum lock count exceeded");
                if (compareAndSetState(c, c + SHARED_UNIT)) {
                    if (sharedCount(c) == 0) {
                        firstReader = current;
                        firstReaderHoldCount = 1;
                    } else if (firstReader == current) {
                        firstReaderHoldCount++;
                    } else {
                        if (rh == null)
                            rh = cachedHoldCounter;
                        if (rh == null || rh.tid != getThreadId(current))
                            rh = readHolds.get();
                        else if (rh.count == 0)
                            readHolds.set(rh);
                        rh.count++;
                        cachedHoldCounter = rh; // cache for release
                    }
                    return 1;
                }
            }
        }


        /**
         * 尝试加写锁(读写锁中)
         */
        final boolean tryWriteLock() {
            Thread current = Thread.currentThread();
            int c = getState();
            // 其他线程持有锁
            if (c != 0) {
                int w = exclusiveCount(c);
                if (w == 0 || current != getExclusiveOwnerThread())
                    return false;
                if (w == MAX_COUNT)
                    throw new Error("Maximum lock count exceeded");
            }

            // 没有线程持有锁
            if (!compareAndSetState(c, c + 1))
                return false;
            setExclusiveOwnerThread(current);
            return true;
        }

        /**
         * Performs tryLock for read, enabling barging in both modes.
         * This is identical in effect to tryAcquireShared except for
         * lack of calls to readerShouldBlock.
         */
        final boolean tryReadLock() {
            Thread current = Thread.currentThread();
            for (; ; ) {
                int c = getState();
                if (exclusiveCount(c) != 0 &&
                        getExclusiveOwnerThread() != current)
                    return false;
                int r = sharedCount(c);
                if (r == MAX_COUNT)
                    throw new Error("Maximum lock count exceeded");
                if (compareAndSetState(c, c + SHARED_UNIT)) {
                    if (r == 0) {
                        firstReader = current;
                        firstReaderHoldCount = 1;
                    } else if (firstReader == current) {
                        firstReaderHoldCount++;
                    } else {
                        HoldCounter rh = cachedHoldCounter;
                        if (rh == null || rh.tid != getThreadId(current))
                            cachedHoldCounter = rh = readHolds.get();
                        else if (rh.count == 0)
                            readHolds.set(rh);
                        rh.count++;
                    }
                    return true;
                }
            }
        }

        protected final boolean isHeldExclusively() {
            // While we must in general read state before owner,
            // we don't need to do so to check if current thread is owner
            return getExclusiveOwnerThread() == Thread.currentThread();
        }

        // Methods relayed to outer class

        final ConditionObject newCondition() {
            return new ConditionObject();
        }

        final Thread getOwner() {
            // Must read state before owner to ensure memory consistency
            return ((exclusiveCount(getState()) == 0) ?
                    null :
                    getExclusiveOwnerThread());
        }

        final int getReadLockCount() {
            return sharedCount(getState());
        }

        final boolean isWriteLocked() {
            return exclusiveCount(getState()) != 0;
        }

        final int getWriteHoldCount() {
            return isHeldExclusively() ? exclusiveCount(getState()) : 0;
        }

        final int getReadHoldCount() {
            if (getReadLockCount() == 0)
                return 0;

            Thread current = Thread.currentThread();
            if (firstReader == current)
                return firstReaderHoldCount;

            HoldCounter rh = cachedHoldCounter;
            if (rh != null && rh.tid == getThreadId(current))
                return rh.count;

            int count = readHolds.get().count;
            if (count == 0) readHolds.remove();
            return count;
        }

        /**
         * Reconstitutes the instance from a stream (that is, deserializes it).
         */
        private void readObject(java.io.ObjectInputStream s)
                throws java.io.IOException, ClassNotFoundException {
            s.defaultReadObject();
            readHolds = new ThreadLocalHoldCounter();
            setState(0); // reset to unlocked state
        }

        final int getCount() {
            return getState();
        }
    }

    /**
     * 非公平锁
     */
    static final class NonfairSync extends Sync {
        private static final long serialVersionUID = -8159625535654395037L;

        final boolean writerShouldBlock() {
            return false; // writers can always barge
        }

        // 读锁状态阻塞
        final boolean readerShouldBlock() {
            return apparentlyFirstQueuedIsExclusive();
        }
    }

    /**
     * 公平锁
     */
    static final class FairSync extends Sync {
        private static final long serialVersionUID = -2274990926593161451L;

        final boolean writerShouldBlock() {
            return hasQueuedPredecessors();
        }

        final boolean readerShouldBlock() {
            return hasQueuedPredecessors();
        }
    }


    /**
     * 读锁
     */
    public static class ReadLock implements Lock, java.io.Serializable {
        private static final long serialVersionUID = -5992448646407690164L;
        private final Sync sync;


        protected ReadLock(ReentrantReadWriteLock lock) {
            sync = lock.sync;
        }

        /**
         * 获取一把读锁
         *  在不同线程中如果有其他的线程获取了写锁，则进入同步队列阻塞，否则获取到这把读锁。
         *  在同一个线程中，如果之前获取了写锁，则可以接着获取，如果之前获取了读锁，则不能获取这把写锁
         */
        public void lock() {
            sync.acquireShared(1);
        }

        /**
         * 与lock一致，但是如果当前线程在阻塞的过程中，别其他的线程中断了，则会抛出中断异常
         */
        public void lockInterruptibly() throws InterruptedException {
            sync.acquireSharedInterruptibly(1);
        }

        /**
         * 只是尝试的来获取读锁，获取到了返回true 获取不到返回false
         */
        public boolean tryLock() {
            return sync.tryReadLock();
        }

        /**
         * 只是尝试的来获取读锁，获取到了返回true ，在指定的时间内还是获取不到，则返回false
         */
        public boolean tryLock(long timeout, TimeUnit unit)
                throws InterruptedException {
            return sync.tryAcquireSharedNanos(1, unit.toNanos(timeout));
        }

        /**
         * 当前线程释放这把读锁
         */
        public void unlock() {
            sync.releaseShared(1);
        }

        /**
         * 读锁，没有实现，调用会抛出UnsupportedOperationException异常
         */
        public Condition newCondition() {
            throw new UnsupportedOperationException();
        }

        public String toString() {
            int r = sync.getReadLockCount();
            return super.toString() +
                    "[Read locks = " + r + "]";
        }
    }

    /**
     * 写锁
     */
    public static class WriteLock implements Lock, java.io.Serializable {
        private static final long serialVersionUID = -4992448646407690164L;
        private final Sync sync;

        protected WriteLock(ReentrantReadWriteLock lock) {
            sync = lock.sync;
        }

        /**
         * 获取写锁。
         * 在不同线程中如果有其他的线程获取了写或者读锁，则进入同步队列阻塞，否则获取到这把写锁。在同一个线程中，可以直接获取到这把锁
         */
        public void lock() {
            sync.acquire(1);
        }

        /**
         * 与lock一致，但是如果当前线程在阻塞的过程中，别其他的线程中断了，则会抛出中断异常
         */
        public void lockInterruptibly() throws InterruptedException {
            sync.acquireInterruptibly(1);
        }

        /**
         * 只是尝试的来获取写锁，获取到了返回true 获取不到返回false
         */
        public boolean tryLock() {
            return sync.tryWriteLock();
        }

        /**
         * 只是尝试的来获取写锁，获取到了返回true ，在指定的时间内还是获取不到，则返回false
         */
        public boolean tryLock(long timeout, TimeUnit unit)
                throws InterruptedException {
            return sync.tryAcquireNanos(1, unit.toNanos(timeout));
        }

        /**
         * 当前线程释放这把写锁
         */
        public void unlock() {
            sync.release(1);
        }

        /**
         * 生成一个等待集合Condition对象
         */
        public Condition newCondition() {
            return sync.newCondition();
        }

        public String toString() {
            Thread o = sync.getOwner();
            return super.toString() + ((o == null) ?
                    "[Unlocked]" :
                    "[Locked by thread " + o.getName() + "]");
        }

        public boolean isHeldByCurrentThread() {
            return sync.isHeldExclusively();
        }

        public int getHoldCount() {
            return sync.getWriteHoldCount();
        }
    }


    // Instrumentation and status


    public final boolean isFair() {
        return sync instanceof FairSync;
    }

    protected Thread getOwner() {
        return sync.getOwner();
    }

    public int getReadLockCount() {
        return sync.getReadLockCount();
    }

    public boolean isWriteLocked() {
        return sync.isWriteLocked();
    }

    public boolean isWriteLockedByCurrentThread() {
        return sync.isHeldExclusively();
    }

    public int getWriteHoldCount() {
        return sync.getWriteHoldCount();
    }

    public int getReadHoldCount() {
        return sync.getReadHoldCount();
    }

    protected Collection<Thread> getQueuedWriterThreads() {
        return sync.getExclusiveQueuedThreads();
    }

    protected Collection<Thread> getQueuedReaderThreads() {
        return sync.getSharedQueuedThreads();
    }

    public final boolean hasQueuedThreads() {
        return sync.hasQueuedThreads();
    }

    public final boolean hasQueuedThread(Thread thread) {
        return sync.isQueued(thread);
    }

    public final int getQueueLength() {
        return sync.getQueueLength();
    }

    protected Collection<Thread> getQueuedThreads() {
        return sync.getQueuedThreads();
    }

    public boolean hasWaiters(Condition condition) {
        if (condition == null)
            throw new NullPointerException();
        if (!(condition instanceof AbstractQueuedSynchronizer.ConditionObject))
            throw new IllegalArgumentException("not owner");
        return sync.hasWaiters((AbstractQueuedSynchronizer.ConditionObject) condition);
    }

    public int getWaitQueueLength(Condition condition) {
        if (condition == null)
            throw new NullPointerException();
        if (!(condition instanceof AbstractQueuedSynchronizer.ConditionObject))
            throw new IllegalArgumentException("not owner");
        return sync.getWaitQueueLength((AbstractQueuedSynchronizer.ConditionObject) condition);
    }

    protected Collection<Thread> getWaitingThreads(Condition condition) {
        if (condition == null)
            throw new NullPointerException();
        if (!(condition instanceof AbstractQueuedSynchronizer.ConditionObject))
            throw new IllegalArgumentException("not owner");
        return sync.getWaitingThreads((AbstractQueuedSynchronizer.ConditionObject) condition);
    }

    public String toString() {
        int c = sync.getCount();
        int w = Sync.exclusiveCount(c);
        int r = Sync.sharedCount(c);

        return super.toString() +
                "[Write locks = " + w + ", Read locks = " + r + "]";
    }

    static final long getThreadId(Thread thread) {
        return UNSAFE.getLongVolatile(thread, TID_OFFSET);
    }






    // Unsafe mechanics
    private static final sun.misc.Unsafe UNSAFE;
    private static final long TID_OFFSET;

    static {
        try {
            UNSAFE = sun.misc.Unsafe.getUnsafe();
            Class<?> tk = Thread.class;
            TID_OFFSET = UNSAFE.objectFieldOffset
                    (tk.getDeclaredField("tid"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }

}
